<?php

/*
Design an algorithm and write code to serialize and deserialize a binary tree. 
Writing the tree to a file is called ‘serialization’ and reading back from the 
file to reconstruct the exact same binary tree is ‘deserialization’.
*/

require_once 'util.php';

importJS();

$arr = generateRandomArray(0, 99, 6);

$root = null;
foreach( $arr as $value ){
	$root = bt_insert($value, $root);
}

$serial = bt_serialize2( $root );

$new = bt_deserialize2( $serial );

bt_draw($root);

echo "Serialized:<br/>";
echo $serial;
echo "<br/>";
echo "Reconstructed:<br/>";
bt_draw($new);

//================================================================================
/*
Solution:
Serialization: Save the BT's preorder and inorder traverse into the file.
Space: O(n) Time: O(n)
Deserialization: Construct back the BT using the pre and in order traversal
Space: O(n) Time: O(n * (n + log n))=O(n^2)
*/
function bt_serialize( $root ){
	if( !$root ){
		return '';
	}
	$inorder = bt_implode_inorder($root);
	$preorder = bt_implode_preorder($root);

	// Serialize by having a inorder and a preorder traversal
	$serial = $inorder . "#" . $preorder;
	return $serial;
}
// Deserialize the bt, assuming the $string is what we have for input
function bt_deserialize( $string ){
	// Get back the inorder and preorder traversal
	$data = explode('#', $string);
	if( 2 != count($data) ){
		return null;
	}
	
	$inorder = explode(' ', trim($data[0]));
	$preorder = explode(' ', trim($data[1]));
	if( count($inorder) != count($preorder) ){
		return null;	
	}

	$root = null;
	foreach( $preorder as $value ){
		bt_deserialize_insert( $value, $root, $inorder );
	}

	return $root;

}

function bt_deserialize_insert( $value, &$root, $inorder ){
	if( !$root ){
		$root = new CBTNode();
		$root->value = $value;
		return;
	}

	// Search for the index in inorder
	for( $index=0; $index<count($inorder); $index++ ){
		if( $inorder[$index] == $root->value ){
			// value should go to root's right
			bt_deserialize_insert( $value, $root->right, $inorder );
			break;
		}
		else if( $inorder[$index] == $value ){
			// value should go to root's left
			bt_deserialize_insert( $value, $root->left, $inorder );
			break;
		}
	}
	return;
}
//================================================================================

//================================================================================
/*
Better Solution:
Is it really necessary to have something other than the preorder?
During insersion from a pre order data, a bst tells you to insert to left or right because of the bst nature.
How to determine if moving into the correct direction?
Telling by putting a special char e.g. "#" at the not supposed to be positions. 
The correct position will be the first (in order) vacancy that is not '#'
*/
function bt_serialize2( $root ){
	if( !$root ){
		return '# ';
	}

	$result = '';
	$result .= "{$root->value} ";
	$result .= bt_serialize2( $root->left );
	$result .= bt_serialize2( $root->right );

	return $result;
}

function bt_deserialize2( $data ){
	$values = explode( ' ', trim($data) );
	if( !count($data) ){
		return null;
	}


	$root = null;
	bt_deserialize_insert2( $values, $root );
	return $root;
}

function bt_deserialize_insert2( &$values, &$root ){

	if( !count($values) ){
		return;
	}

	$cur = array_shift( $values );

	if( $cur == '#' ){
		// Wrong direction, bail out straight away
	}
	else {
		$root = new CBTNode();
		$root->value = $cur;

		bt_deserialize_insert2( $values, $root->left );
		bt_deserialize_insert2( $values, $root->right );
	}
}